package com.github.yangyishe.p300;

/**
 * 300. 最长递增子序列
 * https://leetcode.cn/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 *
 *
 * 示例 1：
 *
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * 示例 2：
 *
 * 输入：nums = [0,1,0,3,2,3]
 * 输出：4
 * 示例 3：
 *
 * 输入：nums = [7,7,7,7,7,7,7]
 * 输出：1
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 2500
 * -104 <= nums[i] <= 104
 *
 *
 * 进阶：
 *
 * 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
 */
public class Problem300 {
    public static void main(String[] args) {
        int[] nums=new int[]{7,7,7,7,7,7,7};

        Problem300 problem300 = new Problem300();
        int length = problem300.lengthOfLIS(nums);
        System.out.println("length = " + length);

    }

    /**
     * 思路:
     * 父问题可以参考子问题, 而不对子问题产生影响.
     * 故本题可用动态规划
     *
     * 维护一个: 低于当前尾元素的最长递增序列集合+1
     * 维护方法: 从尾元素向前遍历, 找到最大的小于尾元素的值, 在此基础上+1, 获得实际要维护的值. 如果没有发现小于尾元素的值, 则值为1.
     * 最大值就在这些尾元素中的最大元素
     *
     * 时间复杂度:O(n^2)
     *
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        //1. 创建维护列表
        int[] tailSeq=new int[nums.length];

        //2. 递归推进
        int actualMax=1;
        for(int i=0;i<nums.length;i++){
            int beforeMax=0;
            for(int j=i-1;j>=0;j--){
                if(nums[j]<nums[i]){
                    beforeMax=Integer.max(beforeMax,tailSeq[j]);
                }
            }
            tailSeq[i]=beforeMax+1;
            actualMax=Integer.max(actualMax,beforeMax+1);
        }

        return actualMax;
    }




    /**
     * 思路:->以下思路不适合该题, 而适合另一种情况, 故先保留
     * 父问题可以参考子问题, 而不对子问题产生影响.
     * 故本题可用动态规划
     *
     * 设置两种最大长度, 连尾最大长度(tailMax)和通常最大长度(max)
     * len=0, tailMax(0)=max(0)=0
     * len=1, tailMax(1)=max(1)=1
     * len=2, if(nums[1]>nums[0]): tailMax(2)=max(2)=2; else max(2)=tailMax(2)=1
     * len=3, if(nums[2]>nums[1]): tailMax(3)=tailMax(2)+1; else tailMax(3)=1. whatever: max(3)=Math.max(tailMax(3),max(2))
     * ...
     * len=n, if(nums[n-1]>nums[n-2]): tailMax(n)=tailMax(n-1)+1; else: tailMax(n)=1. whatever: max(n)=Math.max(tailMax(n),max(n-1))
     *
     * 注1: 由于最后只需要一个max, 所以max不需要维护, 只需要维护tailMax
     * 注2: 0可忽略
     *
     * @param nums
     * @return
     */
    /*public int lengthOfLIS(int[] nums) {
        if (nums.length==1) {
            return 1;
        }
        //1. 创建dp数组
        int[] tailMax=new int[nums.length];
        tailMax[0]=1;
        int max=1;

        //2. 遍历推进
        for(int i=1;i<nums.length;i++){
            if(nums[i]>nums[i-1]){
                tailMax[i]=tailMax[i-1]+1;
            }else{
                tailMax[i]=1;
            }
            max=Integer.max(max,tailMax[i]);
        }

        return max;
    }*/
}
